37. Sliding Blocks Puzzle 1

INSTRUCTOR NOTE:

Why does a h2 expand fewer nodes than h1?

As Peter says, h2 is always greater than or equal to h1. To see why this should expand fewer paths, let's imagine a heuristic h3 that always had the exact cost at every node. This heuristic would naturally expand the least number of nodes.

On the other hand, imagine a heuristic h4 that was always 0. This heuristic would expand the most number of nodes of all possible heuristics.

You can see then that a heuristic that is strictly greater than or equal to another one gets us closer to the perfect heuristic and thereby expands at least the same number of nodes or fewer.